1.1 Field of the Invention
The present invention relates generally to methods and apparatus for signal reconstruction and more specifically to methods and apparatus for recovering sparse signals from finite-range, quantized compressive sensing measurements.
1.2 Brief Description of the Related Art
Analog-to-digital converters (ADCs) are an essential component in digital sensing and communications systems. They interface the analog physical world, where many signals originate, with the digital world, where they can be efficiently analyzed and processed. As digital processors have become smaller and more powerful, their increased capabilities have inspired applications that require the sampling of ever-higher bandwidth signals. This demand has placed a growing burden on ADCs. As ADC sampling rates push higher, they move toward a physical barrier, beyond which their design becomes increasingly difficult and costly. R. Walden, “Analog-to-digital converter survey and analysis,” IEEE J. Selected Areas in Comm., vol. 17, no. 4, pp. 539-550, 1999.
Fortunately, recent theoretical developments in the area of compressive sensing (CS) have the potential to significantly extend the capabilities of current ADCs to keep pace with demand. D. Donoho, “Compressed sensing,” IEEE Trans. Inform. Theory, vol. 6, no. 4, pp. 1289-1306, 2006, E. Candès, “Compressive sampling,” in Proc. Int. Congress Math., Madrid, Spain, August 2006. CS provides a framework for sampling signals at a rate proportional to their information content rather than their bandwidth, as in Shannon-Nyquist systems. In CS, the information content of a signal is quantified as the number of nonzero coefficients in a known transform basis over a fixed time interval M. Vetterli, P. Marziliano, and T. Blu, “Sampling signals with finite rate of innovation,” IEEE Trans. Signal Processing, vol. 50, no. 6, pp. 1417-1428, 2002. Signals that have few nonzero coefficients are called sparse signals. More generally, signals with coefficient magnitudes that decay rapidly are called compressible, because they can be well-approximated by sparse signals. By exploiting sparse and compressible signal models, CS provides a methodology for simultaneously acquiring and compressing signals. This leads to lower sampling rates and thus simplifies hardware designs. The CS measurements can be used to reconstruct the signal or can be directly processed to extract other kinds of information.
The CS framework employs non-adaptive, linear measurement systems and non-linear reconstruction algorithms. In most cases, CS systems exploit a degree of randomness in order to provide theoretical guarantees on the performance of the system. Such systems exhibit additional desirable properties beyond lower sampling rates. In particular, the measurements are democratic, meaning that each measurement contributes an equal amount of information to the compressed representation. This is in contrast to both conventional sampling systems and conventional compression algorithms, where the removal of some samples or bits can lead to high distortion, while the removal of others will have negligible effect.
Several CS-inspired hardware architectures for acquiring signals, images, and videos have been proposed, analyzed, and in some cases implemented. J. Laska, S. Kirolos, M. Duarte, T. Ragheb, R. Baraniuk, and Y. Massoud, “Theory and implementation of an analog-to-information converter using random demodulation,” in Proc. IEEE Int. Symp. Circuits and Systems (ISCAS), New Orleans, La., May 2007, J. Tropp, J. Laska, M. Duarte, J. Romberg, and R. Baraniuk, “Beyond Nyquist: Efficient sampling of sparse, bandlimited signals,” IEEE Trans. Inform. Theory, 2009, J. Romberg, “Compressive sensing by random convolution,” SIAM J. Imaging Sciences, 2009, J. Tropp, M. Wakin, M. Duarte, D. Baron, and R. Baraniuk, “Random filters for compressive sampling and reconstruction,” in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing (ICASSP), Toulouse, France, May 2006, M. Duarte, M. Davenport, D. Takhar, J. Laska, T. Sun, K. Kelly, and R. Baraniuk, “Single-pixel imaging via compressive sampling,” IEEE Signal Processing Mag., vol. 25, no. 2, pp. 83-91, 2008, R. Robucci, L. Chiu, J. Gray, J. Romberg, P. Hasler, and D. Anderson, “Compressive sensing on a CMOS separable transform image sensor,” in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing (ICASSP), Las Vegas, Nev., April 2008, R. Marcia, Z. Harmany, and R. Willett, “Compressive coded aperture imaging,” in Proc. SPIE Symp. Elec. Imaging: Comput. Imaging, San Jose, Calif., January 2009, Y. Eldar and M. Mishali, “Robust recovery of signals from a structured union of subspaces,” IEEE Trans. Inform. Theory, 2009, M. Mishali, Y. Eldar, and J. Tropp, “Efficient sampling of sparse wideband analog signals,” in Proc. Cony. IEEE in Israel (IEEEI), Eilat, Israel, December 2008, M. Mishali and Y. Eldar, “From theory to practice: Sub-Nyquist sampling of sparse wideband analog signals,” Preprint, 2009, Y. Eldar and M. Mishali, “Robust recovery of signals from a structured union of subspaces,” IEEE Trans. Inform. Theory, 2009. The common element in each of these acquisition systems is that the measurements are ultimately quantized, i.e., mapped from real-values to a set of countable values, before they are stored or transmitted. The present invention focuses on this quantization step.
While the effect of quantization on the CS framework has been previously explored L. Jacques, D. Hammond, and M. Fadili, “Dequantizing compressed sensing: When oversampling and non-gaussian contraints combine,” Preprint, 2009, W. Dai, H. Pham, and O. Milenkovic, “Distortion-rate functions for quantized compressive sensing,” Preprint, 2009, A. Zymnis, S. Boyd, and E. Candès, “Compressed sensing with quantized measurements,” Preprint, 2009, J. Sun and V. Goyal, “Quantization for compressed sensing reconstruction,” in Proc. Sampling Theory and Applications (SampTA), Marseille, France, May 2009, prior work has ignored saturation. Saturation occurs when measurement values exceed the saturation level, i.e., the dynamic range of a quantizer. These measurements take on the value of the saturation level. All practical quantizers have a finite dynamic range for one of two reasons, or both: (i) physical limitations allow only a finite range of voltages to be accurately converted to bits and, (ii) only a finite number of bits are available to represent each value. Quantization with saturation is commonly referred to as finite-range quantization.
The challenge in dealing with the errors imposed by finite-range quantization is that, in the absence of an a priori upper bound on the measurements, saturation errors are potentially unbounded. Most CS recovery algorithms only provide guarantees for noise that is either bounded or bounded with high probability (for example, Gaussian noise). E. Candès and T. Tao, “The Dantzig selector: Statistical estimation when p is much larger than n,” Annals of Statistics, vol. 35, no. 6, pp. 2313-2351, 2007. The only exceptions are R. Carrillo, K. Barner, and T. Aysal, “Robust sampling and reconstruction methods for compressed sensing,” in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing (ICASSP), Taipei, Taiwan, April 2009, J. Laska, M. Davenport, and R. Baraniuk, “Exact signal recovery from corrupted measurements through the pursuit of justice,” in Proc. Asilomar Conf. on Signals Systems and Computers, Asilomar, Calif., November 2009, which consider sparse or impulsive noise models, and Z. Harmany, R. Marcia, and R. Willett, “Sparse poisson intensity reconstruction algorithms,” in Proc. IEEE Work. Stat. Signal Processing (SSP), Cardiff, Wales, August 2009, I. Rish and G. Grabarnik, “Sparse signal recovery with exponential-family noise,” in Proc. Allerton Conf. Comm., Control, and Comput., Monticello, Ill., September 2009, which consider unbounded noise from the exponential family of distributions. None of the methods in R. Carrillo, K. Barner, and T. Aysal, “Robust sampling and reconstruction methods for compressed sensing,” in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing (ICASSP), Taipei, Taiwan, April 2009, J. Laska, M. Davenport, and R. Baraniuk, “Exact signal recovery from corrupted measurements through the pursuit of justice,” in Proc. Asilomar Conf. on Signals Systems and Computers, Asilomar, Calif., November 2009, Z. Harmany, R. Marcia, and R. Willett, “Sparse poisson intensity reconstruction algorithms,” in Proc. IEEE Work. Stat. Signal Processing (SSP), Cardiff, Wales, August 2009, I. Rish and G. Grabarnik, “Sparse signal recovery with exponential-family noise,” in Proc. Allerton Conf. Comm., Control, and Comput., Monticello, Ill., September 2009 can be used to handle unbounded quantization errors due to saturation.
1.2.1 Analog-to-Digital Conversion
ADC consists of two discretization steps: sampling, which converts a continuous-time signal to a discrete-time set of measurements, followed by quantization, which converts the continuous value of each measurement to a discrete one chosen from a pre-determined, finite set. Both steps are necessary to represent an analog signal in the discrete digital world.
The discretization step can be lossless or lossy. For example, classical results due to Shannon and Nyquist demonstrate that the sampling step induces no loss of information, provided that the signal is bandlimited and a sufficient number of measurements (or samples) are obtained. Similarly, sensing of images assumes that the image is sufficiently smooth such that the integration of light in each pixel of the sensor is sufficient for a good quality representation of the image. The present description assumes the existence of a discretization that exactly represents the signal, or approximates to sufficient quality. Examples of such discretizations and their implementation in the context of compressive sensing can be found in J. Tropp, J. Laska, M. Duarte, J. Romberg, and R. Baraniuk, “Beyond Nyquist: Efficient sampling of sparse, bandlimited signals,” IEEE Trans. Inform. Theory, 2009, J. Romberg, “Compressive sensing by random convolution,” SIAM J. Imaging Sciences, 2009, J. Tropp, M. Wakin, M. Duarte, D. Baron, and R. Baraniuk, “Random filters for compressive sampling and reconstruction,” in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing (ICASSP), Toulouse, France, May 2006, M. Duarte, M. Davenport, D. Takhar, J. Laska, T. Sun, K. Kelly, and R. Baraniuk, “Single-pixel imaging via compressive sampling,” IEEE Signal Processing Mag., vol. 25, no. 2, pp. 83-91, 2008, R. Robucci, L. Chiu, J. Gray, J. Romberg, P. Hasler, and D. Anderson, “Compressive sensing on a CMOS separable transform image sensor,” in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing (ICASSP), Las Vegas, Nev., April 2008, R. Marcia, Z. Harmany, and R. Willett, “Compressive coded aperture imaging,” in Proc. SPIE Symp. Elec. Imaging: Comput. Imaging, San Jose, Calif., January 2009, Y. Eldar and M. Mishali, “Robust recovery of signals from a structured union of subspaces,” IEEE Trans. Inform. Theory, 2009, M. Mishali, Y. Eldar, and J. Tropp, “Efficient sampling of sparse wideband analog signals,” in Proc. Cony. IEEE in Israel (IEEEI), Eilat, Israel, December 2008, M. Mishali and Y. Eldar, “From theory to practice: Sub-Nyquist sampling of sparse wideband analog signals,” Preprint, 2009, Y. Eldar and M. Mishali, “Robust recovery of signals from a structured union of subspaces,” IEEE Trans. Inform. Theory, 2009. Aspects of such systems in are briefly discussed below in Sec. 1.2.4.
TABLE 1Quantization parameters.Gsaturation levelBnumber of bitsΔbin widthΔ/2maximum error per (quantized) measurementunboundedmaximum error per (saturated) measurement
Instead the present invention focuses on the second aspect of digitization, namely quantization. Quantization results in an irreversible loss of information unless the measurement amplitudes belong to the discrete set defined by the quantizer. A central ADC system design goal is to minimize the distortion due to quantization.
1.2.2 Scalar Quantization
Scalar quantization is the process of converting the continuous value of an individual measurement to one of several discrete values through a non-invertible function R(•). Practical quantizers introduce two kinds of distortion: bounded quantization error and unbounded saturation error.
In this application, the focus is on uniform quantizers with quantization interval Δ. Thus, the quantized values become qk=qo+kΔ, for k ∈, and every measurement g is quantized to the nearest quantization level R(g)=argminqk|g−qk=Δ/2+kΔ, the midpoint of each quantization interval. This minimizes the expected quantization distortion and implies that the quantization error per measurement, |g−R(q)|, is bounded by Δ/2. FIG. 1A depicts the mapping performed by a midrise quantizer.
In practice, quantizers have a finite dynamic range, dictated by hardware constraints such as the voltage limits of the devices and the finite number of bits per measurement of the quantized representation. Thus, a finite-range quantizer represents a symmetric range of values |g|<G, where G>0 is known as the saturation level G. Gray and G. Zeoli, “Quantization and saturation noise due to analog-to-digital conversion,” IEEE Trans. Aerospace and Elec. Systems, vol. 7, no. 1, pp. 222-223, 1971. Values of g between −G and G will not saturate, thus, the quantization interval is defined by these parameters as Δ−2−B+1G. Without loss of generality we assume a midrise B-bit quantizer, i.e., the quantization levels are qk=Δ/2−kΔ, where k=−2B−1, . . . 2B−1−1. Any measurement with magnitude greater than G saturates the quantizer, i.e., it quantizes to the quantization level G−Δ/2, implying an unbounded error. FIG. 1B depicts the mapping performed by a finite range midrise quantizer with saturation level G and Table 1 summarizes the parameters defined with respect to quantization.
1.2.3 Compressive Sensing (CS)
In the CS framework, one acquires a signal x ∈N via the linear measurementsy−Φx+e,  (1)where Φ is an M×N measurement matrix modeling the sampling system, y ∈M is the vector of samples acquired, and e is an M×1 vector that represents measurement errors. If x is K-sparse when represented in the sparsity basis Ψ, i.e., x=Ψα with ∥α∥0:=|supp(α)|≦K, then one can acquire just M=O(K log(N/K)) measurements and still recover the signal x. E. Candès, “Compressive sampling,” in Proc. Int. Congress Math., Madrid, Spain, August 2006, D. Donoho, “Compressed sensing,” IEEE Trans. Inform. Theory, vol. 6, no. 4, pp. 1289-1306, 2006. A similar guarantee can be obtained for approximately sparse, or compressible, signals. Observe that if K is small, then the number of measurements required can be significantly smaller than the Shannon-Nyquist rate.
In E. Candès and T. Tao, “Decoding by linear programming,” IEEE Trans. Inform. Theory, vol. 51, no. 12, pp. 4203-4215, 2005, Candès and Tao introduced the restricted isometry property (RIP) of a matrix Φ and established its important role in CS. From E. Candès and T. Tao, “Decoding by linear programming,” IEEE Trans. Inform. Theory, vol. 51, no. 12, pp. 4203-4215, 2005, we have the definition,